Mr笔记

Appearance

S15-05 算法-树结构 ​

[TOC]

树结构 Tree ​

树 ​

什么是树 ​

真实的树： 相信每个人对现实生活中的树都会非常熟悉。

树的特点：

  • 树通常有一个根。连接着根的是树干。
  • 树干到上面之后会进行分叉成树枝，树枝还会分叉成更小的树枝。
  • 在树枝的最后是叶子。

树的抽象： 专家们对树的结构进行了抽象，发现树可以模拟生活中的很多场景。

模拟树结构 ​

公司组织架构：

image-20250118104714092


红楼梦家谱：

image-20250118105005299


DOM Tree：

image-20250118105018859

树结构的抽象 ​

我们再将里面的数据移除，仅仅抽象出来结构，那么就是我们要学习的树结构

image-20240911170807446

树的优点 ​

我们之前已经学习了多种数据结构来保存数据，为什么要使用树结构来保存数据呢？

树结构和数组/链表/哈希表的对比有什么优点呢？ 树的优点

数组：

优点：

  • 数组的主要优点是根据下标值访问效率会很高。
  • 但是如果我们希望根据元素来查找对应的位置呢？
  • 比较好的方式是先对数组进行排序，再进行二分查找。

缺点：

  • 需要先对数组进行排序，生成有序数组，才能提高查找效率。
  • 另外数组在插入和删除数据时，需要有大量的位移操作(插入到首位或者中间位置的时候)，效率很低。

链表：

优点：

  • 链表的插入和删除操作效率很高。

缺点：

  • 查找效率很低，需要从头开始依次访问链表中的每个数据项，直到找到。
  • 而且即使插入和删除操作效率很高，但是如果要插入和删除中间位置的数据，还是需要重头先找到对应的数据。

哈希表：

优点：

  • 我们学过哈希表后，已经发现了哈希表的插入、查询、删除时效率都是非常高的。

缺点：

  • 空间利用率不高，底层使用的是数组，并且某些单元是没有被利用的。
  • 哈希表中的元素是无序的，不能按照固定的顺序来遍历哈希表中的元素。
  • 不能快速的找出哈希表中的最大值或者最小值这些特殊的值。

树结构：

  • 我们不能说树结构比其他结构都要好，因为每种数据结构都有自己特定的应用场景。
  • 但是树确实也综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构，比如效率一般情况下没有哈希表高)。
  • 并且也弥补了上面数据结构的缺点。

而且为了模拟某些场景，我们使用树结构会更加方便。

  • 因为数结构的非线性的，可以表示一对多的关系。
  • 比如文件的目录结构。

树的术语 ​

在描述树的各个部分的时候有很多术语。为了让介绍的内容更容易理解，需要知道一些树的术语。不过大部分术语都与真实世界的树相关，或者和家庭关系相关(如父节点和子节点)，所以它们比较容易理解。

image-20240911170949280

树的术语：

  • 树(Tree)：n(n≥0)个节点构成的有限集合。

    • 当n=0时，称为空树；

    • 对于任一棵非空树(n> 0)，它具备以下性质：

      • 树中有一个称为“根(Root)”的特殊节点，用 r 表示；
      • 其余节点可分为m(m>0)个互不相交的有限集T₁, T₂, ..., Tₘ，其中每个集合本身又是一棵树，称为原来树的“子树(SubTree)”
  • 根节点(root node)：位于二叉树顶层的节点，没有父节点。
  • 叶节点(leaf node)：没有子节点(度为0)的节点，其两个指针均指向 None 。
  • 子节点(Child)：若A节点是B节点的父节点，则称B节点是A节点的子节点；子节点也称孩子节点。
  • 父节点(Parent)：有子树的节点是其子树的根节点的父节点。
  • 兄弟节点(Sibling)：具有同一父节点的各节点彼此是兄弟节点。
  • 节点所在的层(level)：从顶至底递增，根节点所在层为 1 。
  • 节点的度(degree)：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2 。
  • 节点的深度(depth)：从根节点到该节点所经过的边的数量。
  • 节点的高度(height)：从距离该节点最远的叶节点到该节点所经过的边的数量。
  • 树的高度(height)：从根节点到最远叶节点所经过的边的数量。
  • 边(edge)：连接两个节点的线段，即节点引用(指针)。
  • 路径：从节点n₁到nₖ的路径为一个节点序列n₁，n₂，… ，nₖ。nᵢ是 nᵢ₊₁的父节点。
  • 路径长度：路径所包含边的个数为路径的长度。

image-20250118160809863

树的表示方式 ​

普通表示方式：

image-20250118161911977

js
const ANode = { value: 'A', leftNode: BNode, centerNode: CNode, rightNode: DNode }

儿子-兄弟表示法：

image-20250118162001017

js
const ANode = { value: 'A', sunNode: BNode, siblingNode: null }
const BNode = { value: 'B', sunNode: ENode, siblingNode: CNode }
const CNode = { value: 'C', sunNode: GNode, siblingNode: DNode }

儿子-兄弟表示法旋转：

image-20250118162046791

js
const ANode = { value: 'A', sunNode: BNode, siblingNode: null }
const BNode = { value: 'B', sunNode: ENode, siblingNode: CNode }
const CNode = { value: 'C', sunNode: GNode, siblingNode: DNode }

你发现上面规律了吗？

  • 其实所有的树本质上都可以使用二叉树模拟出来。
  • 所以在学习树的过程中，二叉树非常重要。

二叉树 ​

概述 ​

概念 ​

如果树中每个节点最多只能有两个子节点，这样的树就成为"二叉树"。

前面我们已经提过二叉树的重要性，不仅仅是因为简单，也因为几乎上所有的树都可以表示成二叉树的形式。

二叉树的定义：

  • 二叉树可以为空，也就是没有节点。
  • 若不为空，则它是由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。

二叉树有五种形态：

image-20250118163456373

二叉树的特性 ​

二叉树有几个比较重要的特性，在笔试题中比较常见：

  • 一颗二叉树第i层的最大节点数为：2ⁱ⁻¹，i >= 1;
  • 深度为k的二叉树有最大节点总数为：2ᵏ-1，k >= 1;
  • 对任何非空二叉树T，若n₀表示叶节点的个数、n₂是度为2的非叶节点个数，那么两者满足关系n₀ = n₂ + 1。

image-20250118163550168

完美二叉树 ​

完美二叉树(Perfect Binary Tree，Full Binary Tree，满二叉树)：在二叉树中，除了最下一层的叶节点外，每层节点都有2个子节点，就构成了满二叉树。

image-20250118163612618

完全二叉树 ​

完全二叉树(Complete Binary Tree)：除二叉树最后一层外，其他各层的节点数都达到最大个数。且最后一层从左向右的叶节点连续存在，只缺右侧若干节点。完美二叉树是特殊的完全二叉树。

下面不是完全二叉树，因为D节点还没有右节点，但是E节点就有了左右节点。

image-20250118164551864

二叉树存储 ​

二叉树的存储常见的方式是数组和链表。

数组存储 ​

完全二叉树：按从上至下、从左到右顺序存储

image-20240911171211274

非完全二叉树：非完全二叉树要补全成完全二叉树才可以按照上面的方案存储。但是会造成很大的空间浪费。

image-20240911171222506

链表存储 ​

二叉树最常见的方式还是使用链表存储。

思路：每个节点封装成一个Node，Node中包含存储的数据，左节点的引用，右节点的引用。

image-20250118165512372

二叉搜索树 ​

概述 ​

概念 ​

二叉搜索树(BST，Binary Search Tree，二叉排序树，二叉查找树)：满足以下条件：

  • 1、对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
  • 2、任意节点的左、右子树也是二叉搜索树，即同样满足条件1。

二叉搜索树的上述性质使得它的查找效率非常高。

image-20240911171253288

查找、插入 ​

示例：在二叉搜索树中查找值为10的节点

image-20250118171857170

上述方式就是二分查找的思想

  • 查找所需的最大次数等于二叉搜索树的深度；
  • 插入节点时，也利用类似的方法，一层层比较大小，找到新节点合适的位置。

二叉搜索树实现 ​

API ​

二叉搜索树的常见操作：

插入操作：

  • insert()：(value)，向树中插入一个新的数据。

遍历操作：

  • inOrderTraverse()：()，通过中序遍历方式遍历所有节点。

  • preOrderTraverse()：()，通过先序遍历方式遍历所有节点。

  • postOrderTraverse()：()，通过后序遍历方式遍历所有节点。

  • levelOrderTraverse()：()，通过层序遍历方式遍历所有节点。

查找操作：

  • getMinValue()：()，返回树中最小的值。

  • getMaxValue()：()，返回树中最大的值。

  • search()：(value)，在树中查找一个数据，如果节点存在，则返回true；如果不存在，则返回false。

删除操作：

  • remove()：(value)，从树中移除某个数据。

BSTree 类 ​

我们像封装其他数据结构一样，先来封装一个BSTree的类

图解：

image-20240911171336090

代码解析：

  • 封装BSTree类：
    • 对于BSTree来说，只需要保存根节点即可，因为其他节点都可以通过根节点找到。
  • 封装Node类：还需要封装一个用于保存每一个节点的Node类。
    • 该类包含三个属性：节点对应的value，指向的左子树left，指向的右子树right。

代码实现：

1、封装Node类

image-20250118180217853

2、封装TreeNode类，它继承Node类

image-20250118180232653

3、封装BSTree类

image-20250118180243414

insert() 插入 ​

insert()：(value)，向树中插入一个新的数据。

1、封装insert()方法

image-20250118215656148

2、封装insertNode()方法

image-20250118215944426

3、测试：调用insert()方法。同时安装 hy-algokit 插件，打印生成的树结构

image-20250118220142936


▸ 优化：在类的内部封装打印方法print()

上述的方法中需要在类的外部访问root，不太安全。

image-20250118220648116

遍历二叉搜索树 ​

前面，我们向树中插入了很多的数据，为了能很多的看到测试结果。我们先来学习一下树的遍历。

这里我们学习的树的遍历，针对所有的二叉树都是适用的，不仅仅是二叉搜索树。

树的遍历：

  • 遍历一棵树是指访问树的每个节点(也可以对每个节点进行某些操作，我们这里就是简单的打印)
  • 但是树和线性结构不太一样，线性结构我们通常按照从前到后的顺序遍历，但是树呢？
  • 应该从树的顶端还是底端开始呢？ 从左开始还是从右开始呢？

二叉树常见的遍历方式有四种：

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历
preOrderTraverse() 先序遍历 ​

preOrderTraverse()：()，通过先序遍历方式遍历所有节点。

思路图解：

  • 1、访问根节点
  • 2、先序遍历其左子树
  • 3、先序遍历其右子树

image-20240911171452624

image-20240911171501151


代码实现：递归法

image-20250120145820431


代码实现：非递归法

image-20250120145906995

inOrderTraverse() 中序遍历 ​

inOrderTraverse()：()，通过中序遍历方式遍历所有节点。

遍历过程为：

  • ①中序遍历其左子树；
  • ②访问根节点；
  • ③中序遍历其右子树。

image-20240911171535048

image-20240911171542774


代码实现：递归法

image-20250120150354501


代码实现：非递归法

image-20250120150657362

postOrderTraverse() 后序遍历 ​

postOrderTraverse()：()，通过后序遍历方式遍历所有节点。

遍历过程为：

  • ①后序遍历其左子树；
  • ②后序遍历其右子树；
  • ③访问根节点。

image-20240911171613522

image-20240911171624911


代码实现：递归法

image-20250120150807459


代码实现：非递归法

image-20250120150838608

levelOrderTraverse() 层序遍历 ​

levelOrderTraverse()：()，通过层序遍历方式遍历所有节点。

遍历思路： 层序遍历很好理解，就是从上向下逐层遍历。层序遍历通常我们会借助队列来完成，也是队列的一个经典应用场景；

image-20240911171654990


代码实现：非递归法

image-20250120153834346

获取最值 ​

getMinValue() 最小值 ​

getMinValue()：()，返回树中最小的值。

在二叉搜索树中搜索最值是一件非常简单的事情，其实用眼睛看就可以看出来了。

图解：

image-20250120155719460

代码实现：

image-20250120160159098

getMaxValue() 最大值 ​

getMaxValue()：()，返回树中最大的值。

图解： getMinValue() 最小值

代码实现：

image-20250120160113697

search() 搜索 ​

search()：(value)，在树中查找一个数据，如果节点存在，则返回true；如果不存在，则返回false。

二叉搜索树不仅仅获取最值效率非常高，搜索特定的值效率也非常高。

代码实现：递归法

image-20240911171734172


代码实现：非递归法

image-20250120170219479

remove() 删除 ​

remove()：(value)，从树中移除某个数据。

思路图解：

二叉搜索树的删除有些复杂，我们一点点完成。

1、查找要删除的节点。没有找到则不需要删除。

2、找到后考虑三种情况：

  • 情况一：该节点没有子节点(简单)
  • 情况二：该节点有一个子节点(简单)
  • 情况三：该节点有二个子节点(复杂)

3、情况一：该节点没有子节点(简单)

  • 如果只有一个单独的根，直接删除该根

    image-20250122110630190

  • 如果是叶节点，将该节点的父节点的left或right设为null

    image-20250122102236648

4、情况二：该节点有一个子节点(简单)

  • 如果删除的是根节点，直接将其子节点赋值给root

    image-20250122103546963

  • 修改该节点的父节点直接指向其子节点

    image-20250122110043203

5、情况三：该节点有二个子节点(复杂)

  • 情况1：删除9节点，用9节点的某个后代(8或10)替代9的位置

    image-20250122112732634

  • 情况2：删除7节点，用7节点的某个后代(5或8)替代7的位置，注意： 不是5或9

    image-20250122112841612

  • 情况3：删除15节点，用15的某个后代(14或18)替代15的位置

    image-20250122112955891

  • 规律：被删除节点的后代替代节点，可以是：

    • 去左边找一个比删除节点小一些的节点，但是是左子树的最大节点，该点称为 前驱节点。
    • 去右边找一个比删除节点大一些的节点，但是是右子树的最小节点，该点称为 后继节点。
搜索节点和父节点 ​

image-20250120173227425

重构：搜索节点 ​

remove()和之前的search()方法的代码结构类似，可以合并

1、在search()方法中调用私有方法searchNode()

image-20250120173516629

2、在remove()方法中调用私有方法searchNode()

3、实现抽取的搜索方法searchNode()

image-20250120174045984

4、优化： 同时获取parent节点

  • 为TreeNode节点添加parent属性

    image-20250120174431330

  • 在searchNode()方法中为parent赋值

    image-20250120175100537

  • 在remove()方法中可以通过current获取其父节点

    image-20250120175316790

5、优化： 判断当前节点在其父节点的左边还是右边

  • 为TreeNode节点添加get isLeft()和get isRight()方法

    image-20250120175757503

  • 在remove()方法中调用判断当前节点在其父节点的左边还是右边

情况一：叶节点 ​

  • 如果只有一个单独的根，直接删除该根

    image-20250122110630190

  • 如果是叶节点，将该节点的父节点的left或right设为null

    image-20250122102236648

image-20250120181222607

image-20250120181247918

情况二：一个子节点 ​

  • 如果删除的是根节点，直接将其子节点赋值给root

    image-20250122103546963

  • 修改该节点的父节点直接指向其子节点

    image-20250122110043203

image-20250122110037684

情况三：两个子节点 ​

  • 情况1：删除9节点，用9节点的某个后代(8或10)替代9的位置

    image-20250122112732634

  • 情况2：删除7节点，用7节点的某个后代(5或8)替代7的位置，注意： 不是5或9

    image-20250122112841612

  • 情况3：删除15节点，用15的某个后代(14或18)替代15的位置

    image-20250122112955891

  • 规律：被删除节点的后代替代节点，可以是：

    • 去左边找一个比删除节点小一些的节点，但是是左子树的最大节点，该点称为 前驱节点。
    • 去右边找一个比删除节点大一些的节点，但是是右子树的最小节点，该点称为 后继节点。

1、实现获取后继节点的方法getSuccessor()

image-20250122122900885

2、用后继节点替换被删除的节点

image-20250122123054092

重构：删除节点 ​

image-20250122124054557

插入对象@ ​

我们不但可以在二叉搜索树中存放对象数字，还可以存放对象等类型的数据。

1、创建一个Product产品类

image-20250123155537012

2、通过Product创建对象实例，并插入到bst树中

image-20250123155927949

3、问题：此时插入的对象是没有经过比较的，形成了链结构。

解决思路：可以通过在Product类中，重写valueOf()方法，让对象可以比较price属性。

image-20250123160319789

4、优化：打印树时，显示更多信息。

思路：

  • 导入 hy-algokit 包中的接口 PrintableNode 并implements实现它，以此约束Node类的属性。
  • 在自定义的get value()方法中，返回想要打印的信息。

image-20250123161622438

总结 ​

看到这里，你就会发现删除节点相当棘手。

实际上，因为它非常复杂，一些程序员都尝试着避开删除操作，因此就出现了其他删除节点的思路：

思路一：

  • 1、在Node类中添加一个isDeleted字段。
  • 2、删除某节点时，就设置isDeleted = true。
  • 3、在查找操作时，先判断节点的isDeleted值。
  • 优点：实现起来比较简单，每次删除节点不会改变原有的树结构。
  • 缺点：在存储中依然保留着被删除的节点。

思路二：

  • 1、只修改被删除节点的value值为后继节点的值：delNode.value = successor.value
  • 2、后继节点后的节点结构依然调整。

二叉搜索树的缺陷 ​

优势：二叉搜索树作为数据存储的结构有重要的优势：

可以快速地找到给定关键字的数据项 并且可以快速地插入和删除数据项。

问题： 二叉搜索树有一个很麻烦的问题：插入有序数据 会形成 非平衡树。

如果插入的数据是有序的数据，比如下面的情况：有一棵初始化为 9 8 12 的二叉树，插入下面的数据：7 6 5 4 3

image-20250122125444478

非平衡树(Unbalanced Tree) 指在树的数据结构中，节点的左右子树的高度差异较大，导致树形结构不平衡，可能会影响其性能表现，特别是在查找、插入和删除操作时。查找效率由O(logN)变成了O(N)。

平衡树 ​

为了能以较快的时间O(logN)来操作一棵树，我们需要保证树总是平衡的：

  • 至少大部分是平衡的，那么时间复杂度也是接近O(logN)的
  • 也就是说树中每个节点左边的子孙节点的个数，应该尽可能的等于右边的子孙节点的个数。

常见的平衡树：

  • AVL树：是最早的一种平衡树，它通过在每个节点多存储一个额外的数据保持树的平衡。时间复杂度为O(logN)。

  • 红黑树：也通过一些特性来保持树的平衡。时间复杂度为O(logN)。

  • 对比： 插入/删除等操作，红黑树性能优于AVL树。红黑树因此应用更多。

平衡二叉树 ​

平衡树 Balanced Tree ​

平衡树(Balanced Tree) 是一种特殊的二叉搜索树，其目的是通过一些特殊的技巧来维护树的高度平衡。从而保证树的搜索、插入、删除等操作的时间复杂度都较低。

为什么需要平衡树：

一棵树如果退化成链状结构，那么搜索、插入、删除等操作的时间复杂度就会达到最坏情况，即O(n)。

平衡树通过不断调整树的结构，使得树的高度尽量平衡，从而保证搜索、插入、删除等操作的时间复杂度都较低，通常为O(logn)。因此，如果我们需要高效地处理大量的数据，那么平衡树就显得非常重要了。

应用： 平衡树的应用非常广泛，如索引、内存管理、图形学等领域均有广泛使用。


插入有序数字导致树不平衡：

比如我们连续的插入1、2、3、4、5、6的数字，那么前面的二叉搜索树最终形成的结构如下

image-20250123120901811


删除元素导致树不平衡：

事实上不只是添加会导致树的不平衡，删除元素也可能会导致树的不平衡。

image-20250127125423356

平衡树的方式 ​

方式一：限制插入、删除节点。在树特性的状态下，不允许插入或者删除某些节点，不现实。

方式二：使用特定方式再平衡树。在随机插入或者删除元素后，通过某种方式观察树是否平衡，如果不平衡通过特定的方式（比如旋转），让树保持平衡。

image-20250123120918428

常见的平衡二叉搜索树 ​

常见的平衡二叉搜索树有哪些呢？

  • AVL树：这是一种最早的平衡二叉搜索树，在1962年由G.M. Adelson-Velsky和E.M. Landis发明。
  • 红黑树：这是一种比较流行的平衡二叉搜索树，由R. Bayer在1972年发明。
  • Splay树：这是一种动态平衡二叉搜索树，通过旋转操作对树进行平衡。
  • Treap：这是一种随机化的平衡二叉搜索树，是二叉搜索树和堆的结合。
  • B-树：这是一种适用于磁盘或其他外存存储设备的多路平衡查找树。

这些平衡二叉搜索树都用于保证搜索树的平衡，从而在插入、删除、查找操作时保证了较低的时间复杂度。

红黑树和AVL树是应用最广泛的平衡二叉搜索树：

  • 红黑树：红黑树被广泛应用于实现诸如操作系统内核、数据库、编译器等软件中的数据结构，其原因在于它在插入、删除、查找操作时都具有较低的时间复杂度。
  • AVL树：AVL树被用于实现各种需要高效查询的数据结构，如计算机图形学、数学计算和计算机科学研究中的一些特定算法。

AVL树 ​

概述 ​

AVL树(Adelson-Velsky and Landis Tree) 是一种自平衡的二叉搜索树，其特点是通过维护每个节点的平衡因子来保持树的平衡。插入或删除节点后，若树不平衡，需要通过旋转操作（单旋转或双旋转）来恢复平衡。

AVL树的平衡因子 是该节点左子树的高度减去右子树的高度，平衡因子的绝对值不能大于1。

  • 在AVL树中，任意节点的平衡因子只有1或-1或0，因此AVL树也被称为高度平衡树。
  • 对于每个节点，它的左子树和右子树的高度差不超过1。
  • 这使得AVL树具有比普通的二叉搜索树更高的查询效率。
  • 当插入或删除节点时，AVL树可以通过旋转操作来重新平衡树，从而保证其平衡性。

由于AVL树具有自平衡性，因此其最坏情况下的时间复杂度仅O(logn)。

image-20250123120936579

旋转操作 ​

AVL树的插入和删除操作与普通的二叉搜索树类似，但是在插入或者删除之后，需要继续保持树的平衡。

  • AVL树需要通过旋转操作来维护平衡。
  • 有四种情况旋转操作：左左情况、右右情况、左右情况和右左情况双旋。
  • 具体使用哪一种旋转，要根据不同的情况来进行区分和判断。

image-20250123120950466

AVL树的实现 ​

手写实现AVL树本身的过程是相当的复杂的，所以对于它的学习路线我进行了专门的设计。

我们如何学习呢？

  • 步骤一：学习AVL树节点的封装。
  • 步骤二：学习AVL树的旋转情况下如何编写代码。
  • 步骤三：写出不同情况下进行的不同旋转操作。
  • 步骤四：写出插入操作后，树的再平衡操作。
  • 步骤五：写出删除操作后，树的再平衡操作。

我们可以通过分治的思想，一步步实现上面的功能，再将功能组合在一起就完成了AVL树的编写过程。

节点的封装 ​

封装-AVLTreeNode ​

image-20250127151045117

封装-getHeight() ​

image-20250127151917916

测试：

image-20250127151930763

封装-getBalanceFactor() ​

image-20250127152418225

测试：

image-20250127152259757

封装-isBalanced ​

image-20250127152618546

测试：

image-20250127152752226

封装-higherChild ​

image-20250127153432097

测试：

image-20250127153532506

封装-旋转-rightRotation() ​

实现步骤： 核心就是要修改变化节点的3个属性(指针)：parent、left、right。

  • 处理pivot节点：

    • 1、pivot = root.left：选择当前节点的左子节点作为旋转轴心。
    • 2、pivot.parent = root.parent：pivot的父节点指向root节点的父节点。

  • 处理pivot右子节点：

    • 3、root.left = pivot.right：root节点的左节点,指向pivot的右节点。
    • 4、pivot.right.parent = root：如果右节点有值, 那么右节点的父节点指向root节点。

  • 处理root节点：

    • 5、pivot.right = root：pivot的右节点指向root。
    • 6、root.parent = pivot：root节点的父节点指向pivot。

  • 挂载pivot节点：

    • 7、pivot.parent = null：如果pivot没有父节点，avltree.root = pivot。
    • 8、root.isLeft = true：如果pivot是父节点的左子节点，pivot.parent.left = pivot。
    • 9、root.isRight= true：如果pivot是父节点的右子节点，pivot.parent.right = pivot。

图解：

image-20250127162137900


代码实现：

image-20250127163526656

测试：

image-20250127164419059

封装-旋转-leftRotation() ​

实现步骤： 核心就是要修改变化节点的3个属性(指针)：parent、left、right。

  • 处理pivot节点： root.right
    • 1、pivot = root.right：选择当前节点的右子节点作为旋转轴心。
    • 2、pivot.parent = root.parent：pivot的父节点指向root节点的父节点。
  • 处理pivot左子节点：pivot.left
    • 3、root.right = pivot.left：root节点的右子节点,指向pivot的左子节点。
    • 4、pivot.left.parent = root：如果左子节点有值, 那么左子节点的父节点指向root节点。
  • 处理root节点：root(this)
    • 5、pivot.left = root：pivot的左子节点指向root。
    • 6、root.parent = pivot：root节点的父节点指向pivot。
  • 挂载pivot节点：pivot.parent
    • 7、pivot.parent = null：如果pivot没有父节点，avltree.root = pivot。
    • 8、root.isLeft = true：如果pivot是父节点的左子节点，pivot.parent.left = pivot。
    • 9、root.isRight= true：如果pivot是父节点的右子节点，pivot.parent.right = pivot。

图解：

image-20250127171643627


代码实现：

image-20250127172851213

测试：

image-20250127173249474

AVL树的封装 ​

封装-AVLTree ​

image-20250127174350455

测试：

image-20250127174343444

封装-rebalance() ​

旋转的四种情况 - 分析

如何对AVL树进行旋转呢？

首先，我们需要先找到失衡的节点：

  • 失衡的节点称之为grandParent
  • 失衡节点的儿子（更高的儿子）称之为parent
  • 失衡节点的孙子（更高的孙子）称之为current

如果从grandParent到current的是：

  • LL：左左情况，那么右旋转；
  • RR：右右情况，那么左旋转；
  • LR：左右情况，那么先对parent进行左旋转，再对grandParent进行右旋转；
  • RL：右左情况，那么先对parent进行右旋转，再对grandParent进行左旋转；

image-20250123121117264

旋转的四种情况 - 代码实现 ​

image-20250123121128072

LL的案例演示 ​

image-20250123121143389

插入的案例演示 ​

image-20250123121203517

image-20250123121210454

insert的调整和再平衡 ​

我们可以继续使用之前的插入操作，在插入完成后去检查树的平衡：

image-20250123121221250

image-20250123121228292

细节一 – Node节点的类型 ​

这里有一个小细节 - BSTree插入的节点类型 TreeNode

我们可以封装一个模板方法，让子类来进行重写即可

image-20250123121240986

image-20250123121247611

细节二 – Node节点需要保存父节点 ​

因为之后我们需要从当前节点中寻找parent节点，所以最好让每一个节点都保存一份parent节点（之前代码是不需要的）

image-20250123121258111

随机插入数据的案例演示 ​

我们可以随机一些数字，插入到AVLTree中来查看树是否平衡：

image-20250123121308245

image-20250123121314730

删除的案例演示 ​

image-20250123121330425

remove的调整和再平衡 ​

image-20250123121347587

问题 – checkBalance传入谁？ ​

思考： checkBalance传入谁？

  • 很明显应该是删除的节点；
  • 但是如果有两个子节点的情况，我们需要找的是前期和后继，最终是将前驱和后继位置的节点删除掉的；
  • 寻找的应该是从AVL树中被移除位置的节点；

情况一：删除节点本身是叶子节点

  • 传入current节点即可，并且需要根据current节点的parent去寻找失衡节点；

情况二：删除节点只有一个子节点

  • 传入current节点即可，并且需要根据current节点的parent去寻找失衡节点；

情况三：删除节点有两个子节点：

  • 找到后继节点successor原来的位置，并且需要根据successor节点去寻找失衡节点；

这里的关键点是两个：

  • 关键点一：必须要找到检测位置的节点；
  • 关键点二：检测位置的节点必须有父节点；

关键点一 – 寻找delNode节点 ​

image-20250123121409550

关键点二 – delNode节点的父节点 ​

情况一和情况二：

  • delNode节点有正确的父节点，但是后面的替换节点会失去正确的父节点；

image-20250123121421959

关键点二 – delNode节点的父节点 ​

情况三：

  • 如果需要找后继节点，那么父节点的操作会比较复杂；
  • 我们可以利用我之前提到的第二种方案，来减少一些父节点的设置操作；

image-20250123121440945

image-20250123121449564

随机插入和删除测试 ​

我们可以随机一些数字，插入，再删除，AVLTree中来查看树是否平衡：

image-20250123121500622

rebalance的优化 ​

目前我们rebalance的操作是哪些节点会执行呢？

  • 插入节点的所有父节点（一直向上查找父节点）；
  • 删除节点的所有父节点（一直向上查找父节点）；

但是 是否需要每次插入、删除都需要将所有的父节点都rebalance操作呢？

  • 这个取决于在插入一个节点后后，是否改变了祖父节点的高度；
  • 这个取决于在删除一个节点后后，是否改变了祖父节点的高度；

image-20250123121513614

image-20250123121521153

我们得出结论：

  • 插入节点，再平衡rebalance后不需要继续后续节点的再平衡rebalance ；
  • 删除节点，再平衡rebalance后需要继续后续节点的再平衡rebalance；

如何优化代码 ​

image-20250123121529995

邂逅 红黑树 ​

首先，红黑树是数据结构中很难的一个知识点，难到什么程度呢?

  • 基本你跟别人聊数据结构的时候, 他不会和你聊红黑树, 因为它是数据结构中一个难点中的难点.
  • 数据结构的学习本来就比较难了, 红黑树是又将难度上升一个档次的知识点.

面试的时候经常出现这个场景:

  • 面试官: 你知道红黑树吗?
  • 面试者: 知道啊。
  • 面试官: 知道原理吗?
  • 面试者: 不知道啊。
  • 面试官: 那你让‘不’过来面试我们公司吧，你先回去等通知吧。

哪些面试会出现红黑树呢?

  • 在面试时基本不会让手写红黑树（即使是面试Google、Apple这样的公司，也很少会出现）。
  • 通常是这样问题的（比如腾讯的一次面试题）：为什么已经有平衡二叉树（比如AVL树）了，还需要红黑树呢？

红黑树的介绍 ​

红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构。

  • 它在1972年由鲁道夫·贝尔发明，被称为“对称二叉B树”，它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。

红黑树, 除了符合二叉搜索树的基本规则外, 还添加了一下特性:

  • 1.节点是红色或黑色。
  • 2.根节点是黑色。
  • 3.每个叶子节点都是黑色的空节点（NIL节点，空节点）。
    • 第三条性质要求每个叶节点（空节点）是黑色的
    • 这是因为在红黑树中，黑色节点的数量表示从根节点到该节点的黑色节点数量。
  • 4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    • 第四条性质保证了红色节点的颜色不会影响树的平衡，同时保证了红色节点的出现不会导致连续的红色节点。
  • 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
    • 第五条性质是最重要的性质，保证了红黑树的平衡性。

这些规则会让人一头雾水

  • 完成搞不懂规则叠加起来，怎么让一棵树平衡的。
  • 但是它们还是被一些聪明的人发明出来了。

红黑树的图例 ​

image-20250123121557674

红黑树的相对平衡 ​

前面的性质约束，确保了红黑树的关键特性:

  • 从根到叶子的最长可能路径, 不会超过最短可能路径的两倍长。
  • 结果就是这个树基本是平衡的.
  • 虽然没有做到绝对的平衡，但是可以保证在最坏的情况下, 依然是高效的。

为什么可以做到 最长路径不超过最短路径的两倍 呢？

  • 性质五决定了最短路径和最长路径必须有相同的黑色节点；
  • 路径最短的情况：全部是黑色节点n；
  • 路径最长的情况：首尾解释黑色节点n，中间全部是红色节点n – 1；
    • 性质二：根节点是黑节点；
    • 性质三：叶子节点都是黑节点；
    • 性质四：两个红色节点不能相连
  • 最短路径为 n – 1（边的数量）；
  • 最长路径为 (n + n – 1) - 1 = 2n – 2；
  • 所以 最长路径 一定不超过 最短路径的2倍；

红黑树的代码实现 ​

手写一个 TypeScript 红黑树的详细步骤：

  • 定义红黑树的节点：定义一个带有键、值、颜色、左子节点、右子节点和父节点的类；
  • 实现左旋操作：将一个节点向左旋转，保持红黑树的性质；
  • 实现右旋操作：将一个节点向右旋转，保持红黑树的性质；
  • 实现插入操作：在红黑树中插入一个新的节点，并保持红黑树的性质；
  • 实现删除操作：从红黑树中删除一个节点，并保持红黑树的性质；
  • 实现修复红黑树性质：在插入或删除操作后，通过旋转和变色来修复红黑树的性质；
  • 其他方法较为简单，可以自行实现；

具体代码参考我的Markdown笔记。

红黑树的性能分析 ​

事实上，红黑树的性能在搜索上是不如AVL树的，为什么呢？

我们来看一下右边的红黑树：

  • 首先，它符合是一颗红黑树吗？符合。
  • 这个时候我们插入 节点30，会被插入到哪里呢？
    • 27的右边，并且节点30是红色节点时，依然符合红黑树的性质。
  • 也就是对于红黑树来说，它不需要进行任何操作；

那么AVL树会怎么样呢？

  • 如果是AVL树必然要对17、25、27节点进行右旋转；
  • 事实上右旋转是一系列的操作；

但是红黑树的高度比AVL树要高：

  • 所以如果同样是搜索30，那么红黑树需要搜索4次，AVL树搜索3次；
  • 所以红黑树相当于牺牲了一点点的搜索性能，来提高了插入和删除的性能；

image-20250123121652943

image-20250123121659487

AVL树和红黑树的选择 ​

AVL树和红黑树的性能对比：

  • AVL树是一种平衡度更高的二叉搜索树，所以在搜索效率上会更高；
  • 但是AVL树为了维护这种平衡性，在插入和删除操作时，通常会进行更多的旋转操作，所以效率相对红黑树较低；
  • 红黑树在平衡度上相较于AVL树没有那么严格，所以搜索效率上会低一些；
  • 但是红黑树在插入和删除操作时，通常需要更少的旋转操作，所以效率相对AVL树较高；
  • 它们的搜索、添加、删除时间复杂度都是O(logn)，但是细节上会有一些差异；

开发中如何进行选择呢？

  • 选择AVL树还是红黑树，取决于具体的应用需求。
  • 如果需要保证每个节点的高度尽可能地平衡，可以选择AVL树。
  • 如果需要保证删除操作的效率，可以选择红黑树。

在早期的时候，很多场景会选择AVL树，目前选择红黑树的越来越多（AVL树依然是一种重要的平衡树）。

  • 比如操作系统内核中的内存管理；
  • 比如Java的TreeMap、TreeSet底层的源码；